Es geht also weiterhin erstmal um Dinge, die Wiederholung sein sollten.

Insbesondere heute eben Nicht-Determinismus und die Definition der grundsätzlichen Komplexitätsklassen,

die uns interessieren. Ja, fangen wir an mit Nicht-Determinismus.

Nicht-Determinismus kann ich ja nun in viele verschiedene Berechnungsmodelle einführen.

Bei der Turing-Maschine gibt es da auch verschiedene Alternativen, die wir hier benutzen.

Folgend Aurora und Barak ist vielleicht nicht ganz die übliche. Wir machen das so.

Die Mechanik der Turing-Maschine oder einer bestimmten Turing-Maschine ist immer ja bestimmt

durch ihre Transitionsfunktion, die uns also sagt, in Abhängigkeit von aktuellen Zustand

und gelesenen Bandsymbolen machen wir das und das.

Dann machen wir das und das. Da genau wird der Nicht-Determinismus eingeführt.

Bisher war die Maschine deterministisch, also solange wir die Bandsymbole kennen und

den aktuellen Zustand wissen wir, was wir machen.

Nicht-Determinismus heißt eben gerade, dass es Auswahlmöglichkeiten gibt.

Wir definieren hier ein Modell, wo es dann genau zwei Auswahlmöglichkeiten gibt.

Das heißt, wir haben zwei solche Funktionen, die weiter dasselbe Profil haben wie ursprünglich.

Das heißt, sie hängen ab von aktuellen Zustand und k-gelesenen Bandsymbolen und sie spucken

aus einen neuen Zustand k-1-Symbolen, die geschrieben werden.

Leserband schreiben wir ja nicht und k-Steuerbefehle an die k-Leseköpfe.

Aber wie gesagt, davon gibt es jetzt eben anders als vorher zwei Stück.

Wir stellen uns vor, dass die Maschine in jedem Schritt, den sie macht, sich einfach aussucht,

ob sie sich gemäß Delta 0 oder Delta 1 entwickelt.

Genau so gut hätte ich dieses 0 und 1 natürlich hier als ein extra Argument in die Funktion

schreiben können.

So ein binäres Flag, links lang, rechts lang.

Es wird eben nicht deterministisch ausgewählt, ob wir links lang oder rechts lang laufen.

Wenn man das vergleicht mit Definitionen, die man auch weit verbreitet findet, insbesondere

wenn man es auf Wikipedia nachguckt oder sowas, dann sieht man, dass das da etwas anders definiert

ist, nämlich dass wir aus der Zustandsübergangsfunktion eine Relation machen.

Das heißt also, dass jetzt hier gar nicht mehr rechtseindeutig bestimmt ist, was raus

kommt, sondern einfach beliebig viele Nachfolgezustände da sein können.

Das ist aber im Wesentlichen kein Unterschied.

Es ist halt einfach nur die Frage, haben wir zwei Auswahlmöglichkeiten oder N-Auswahlmöglichkeiten?

Gut, wie simulieren wir N-Auswahlmöglichkeiten mit zwei Auswahlmöglichkeiten?

Naja, wir machen halt diese zwei Auswahlmöglichkeiten so lange nacheinander, bis wir halt mit zwei

hoch dieser Anzahl Wiederholungen eben N erreicht haben.

Das heißt

also gegenüber einem beliebig verzweigenden Nicht-Determinismus haben wir schon einen Slowdown,

weil wir halt eine simultane Auswahl oder eine instantane Auswahl zwischen N-Möglichkeiten

ersetzen müssen durch einen Haufen binären Auswahlmöglichkeiten, die wir hintereinander

schalten.

Da haben wir bei dieser Simulation einen Slowdown.

Ja, überlegen wir uns kurz, wie groß dieser Slowdown ist.

Wenn wir, was weiß ich, K-Auswahlmöglichkeiten haben, dann müssen wir K halbieren, bis wir

nur noch bei einer Möglichkeit da sind.

Das heißt, wir haben also Logarithmus der Anzahl Auswahlmöglichkeiten.

Wie viele Auswahlmöglichkeiten kann es geben?

Nur so viele Dinge, wie hier rechts steht.

Das hängt also ab von, naja, Anzahl Bender, hier nochmal Anzahl Bender, Größe des Alphabets,

Anzahl Zustände.

Das heißt, der Slowdown, der hängt nur ab von der Maschine.